#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 5e4 + 5;
const int INF = 2147483647;

int n, m;
int a[N];
struct Node {
  int val, sz;
  int fa, ch[2];
} tr[N * 80];
#define val(p) tr[p].val
#define sz(p) tr[p].sz
#define fa(p) tr[p].fa
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
int newnode(int v) {
  static int tot = 0;
  ++tot;
  val(tot) = v;
  sz(tot) = 1;
  fa(tot) = lc(tot) = rc(tot) = 0;
  return tot;
}
void pushup(int p) { sz(p) = sz(lc(p)) + sz(rc(p)) + 1; }
void rotate(int x) {
  int y = fa(x), z = fa(y);
  int k = rc(y) == x;
  if (z) tr[z].ch[rc(z) == y] = x;
  fa(x) = z;
  tr[y].ch[k] = tr[x].ch[k ^ 1];
  fa(tr[x].ch[k ^ 1]) = y;
  tr[x].ch[k ^ 1] = y;
  fa(y) = x;
  pushup(y), pushup(x);
}
void splay(int& root, int x, int k) {
  while (fa(x) != k) {
    int y = fa(x), z = fa(y);
    if (z != k) {
      if ((rc(y) == x) ^ (rc(z) == y))
        rotate(x);
      else
        rotate(y);
    }
    rotate(x);
  }
  if (!k) root = x;
}
void insert(int& root, int v) {
  int x = root, p = 0;
  while (x) p = x, x = tr[x].ch[val(x) < v];
  x = newnode(v);
  fa(x) = p;
  tr[p].ch[val(p) < v] = x;
  splay(root, x, 0);
}
void del(int& root, int v) {
  int x = root;
  while (val(x) != v && tr[x].ch[val(x) < v]) x = tr[x].ch[val(x) < v];
  splay(root, x, 0);
  int l = lc(x), r = rc(x);
  while (rc(l)) l = rc(l);
  while (lc(r)) r = lc(r);
  splay(root, l, 0);
  splay(root, r, l);
  lc(r) = 0;
  splay(root, r, 0);
}
int get_rk(int root, int v) {
  int x = root;
  int res = 0;
  while (x) {
    if (val(x) < v)
      res += sz(lc(x)) + 1, x = rc(x);
    else
      x = lc(x);
  }
  return res;
}
int get_pre(int root, int v) {
  int x = root;
  int res = -INF;
  while (x) {
    if (val(x) < v)
      res = val(x), x = rc(x);
    else
      x = lc(x);
  }
  return res;
}
int get_suc(int root, int v) {
  int x = root;
  int res = INF;
  while (x) {
    if (val(x) > v)
      res = val(x), x = lc(x);
    else
      x = rc(x);
  }
  return res;
}
int rt[N << 2];
void build(int p, int l, int r) {
  insert(rt[p], -INF), insert(rt[p], INF);
  rep(i, l, r) insert(rt[p], a[i]);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
}
int query_rk(int L, int R, int x, int p, int l, int r) {
  if (L <= l && R >= r) return get_rk(rt[p], x) - 1;
  int res = 0;
  int mid = (l + r) >> 1;
  if (L <= mid) res += query_rk(L, R, x, p << 1, l, mid);
  if (R > mid) res += query_rk(L, R, x, p << 1 | 1, mid + 1, r);
  return res;
}
int query_val(int L, int R, int k) {
  int l = 1, r = 1e8;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int cnt = query_rk(L, R, mid, 1, 1, n) + 1;
    if (cnt <= k)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return r;
}
void update(int pos, int x, int p, int l, int r) {
  del(rt[p], a[pos]);
  insert(rt[p], x);
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(pos, x, p << 1, l, mid);
  else
    update(pos, x, p << 1 | 1, mid + 1, r);
}
int query_pre(int L, int R, int x, int p, int l, int r) {
  if (L <= l && R >= r) return get_pre(rt[p], x);
  int res = -INF;
  int mid = (l + r) >> 1;
  if (L <= mid) res = max(res, query_pre(L, R, x, p << 1, l, mid));
  if (R > mid) res = max(res, query_pre(L, R, x, p << 1 | 1, mid + 1, r));
  return res;
}
int query_suc(int L, int R, int x, int p, int l, int r) {
  if (L <= l && R >= r) return get_suc(rt[p], x);
  int res = INF;
  int mid = (l + r) >> 1;
  if (L <= mid) res = min(res, query_suc(L, R, x, p << 1, l, mid));
  if (R > mid) res = min(res, query_suc(L, R, x, p << 1 | 1, mid + 1, r));
  return res;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  build(1, 1, n);
  while (m--) {
    int op, x, y, z;
    cin >> op;
    if (op == 3)
      cin >> x >> y;
    else
      cin >> x >> y >> z;
    if (op == 1) cout << query_rk(x, y, z, 1, 1, n) + 1 << endl;
    if (op == 2) cout << query_val(x, y, z) << endl;
    if (op == 3) update(x, y, 1, 1, n), a[x] = y;
    if (op == 4) cout << query_pre(x, y, z, 1, 1, n) << endl;
    if (op == 5) cout << query_suc(x, y, z, 1, 1, n) << endl;
  }
  return 0;
}